from data_structures.stack.array_stack import ArrayStack
def infix_to_postfix(infixexpr):
    prec = {}   #操作符优先级
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = ArrayStack()  #存操作符
    postfixList = []  #后缀表达式列表

    tokenList = list(infixexpr)
    print('中缀表达式字符串列表：',tokenList)
    num = "0123456789"
    for token in tokenList:
        if token in num:
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            '''  
            操作符栈顶为空 +-*/ 直接入栈 
            如果操作符栈顶非空   新操作符与栈顶操作符比较优先级  
                栈顶操作符优先级高于或等于新操作符优先级 则弹出栈顶操作符
                直到新操作符优先级 大于栈顶操作符
            '''
            while (not opStack.is_empty()) and \
                  (prec[opStack.peek()] >= prec[token]):
                  postfixList.append(opStack.pop())
            opStack.push(token)

    while not opStack.is_empty():
        postfixList.append(opStack.pop())

    return " ".join(postfixList)

if __name__ == "__main__":
    expression = "(3+5)*(5+8*4)"
    # expression = "3*5+8-3"
    print("Infix notation: " + expression)
    print("Postfix notation: " + infix_to_postfix(expression))
